//洛谷p1168
#include <bits/stdc++.h>
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
priority_queue<int> L;                            // L取出最重
priority_queue<int, vector<int>, greater<int>> R; // R取出最轻
int main()
{
    int n, m, a, b; // n是数据个数,m是中位数
    scanf("%d%d", &n, &m);
    printf("%d\n", m);
    for (int i = 1; i <= (n - 1) / 2; i++)
    {
        scanf("%d%d", &a, &b);
        if (max(a, b) < m)
        {
            L.push(a), L.push(b), R.push(m);
            m = L.top();
            L.pop();
            printf("%d\n", m);
        }
        else if (min(a, b) > m)
        {
            R.push(a), R.push(b), L.push(m);
            m = R.top();
            R.pop();
            printf("%d\n", m);
        }
        else
        {
            L.push(min(a, b)), R.push(max(a, b));
            printf("%d\n", m);
        }
    }
    if ((n - 1) % 2 == 1)
    {
        scanf("%d", &a);
    }
}